package com.it.data_linkedList.leetcode;

/**
 * @Author: Coke
 * @DateTime: 2023/06/05/21:40
 * @注释: 删除链表的倒数第N个节点
 **/
public class E03LeetCode19 {
    /**
     * @param head: 头链表
     * @param val:  第 N 个节点
     * @return ListNode
     * @作者: Coke
     * @注释: 方法一（递归）
     * @DateTime: 2023/6/5 22:00
     */
    public static ListNode removeNodeFromEnd (ListNode head, int val) {
        ListNode node = new ListNode(- 1, head); // 哨兵
        toRemoveNodeFromEnd(node, val);
        return node.next;
    }
    
    // 执行逻辑
    private static int toRemoveNodeFromEnd (ListNode head, int val) {
        if (head == null) {
            return 0;
        }
        int i = toRemoveNodeFromEnd(head.next, val);// 下一个节点的倒数位置
        if (i == val) {
            head.next = head.next.next;
        }
        return i + 1;
    }
    
    /**
     * @param head:
     * @param n:
     * @return ListNode
     * @作者: Coke
     * @注释: 方法二
     * @DateTime: 2023/6/5 22:29
     */
    public static ListNode removeNodeFromEnd2 (ListNode head, int n) {
        ListNode node = new ListNode(- 1, head); // 哨兵
        ListNode n1 = node;
        ListNode n2 = node;
        for (int i = 0; i < n + 1; i++) {
            n2 = n2.next;
        }
        while (n2 != null) {
            n1 = n1.next;
            n2 = n2.next;
        }
        n1.next = n1.next.next;
        return node.next;
    }
}
